#include"heap.h"

int Less(HeapType a, HeapType b){
    return a < b;
}

void HeapInit(Heap* heap, Compare compare){
    heap->size = 0;
    heap->cmp = compare;
}

void Swap(HeapType* a, HeapType* b){
    HeapType tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

/**
 * @brief 
 * 
 * @param data 
 * @param size 堆的大小
 * @param cmp compare function
 * @param index 堆最后一个叶子节点的id, 一般为len-1
 */
void AdjustUp(HeapType data[], int size, Compare cmp, int index){
    // 节点id从0开始， i---父节点， 2*i+1--->lchild, 2*i+2---rchild;
    int child = index;
    int parent = (child - 1) / 2;

    while(child > 0){
        // 比较子节点与父节点的关系
        if(cmp(data[child], data[parent])){
            Swap(&data[child], &data[parent]);
        }else{
            break;
        }
        // 交换父节点与子节点之后，可能导致上层的堆结果被破坏，因此需要继续比较
        child = parent; // 将当前父节点作为新的子节点，然后计算新的父节点，继续比较
        parent = (child - 1) / 2;
    }
}

/**
 * @brief 
 * 
 * @param data 
 * @param size 
 * @param cmp 
 * @param index 非叶子节点的id,某个父节点
 */
void AdjustDown(HeapType data[], int size, Compare cmp, int index){

    int parent = index;
    int child = parent * 2 +1;
    while(child<size){
        // 先比较相邻的2个子节点
        if(child+1<size && cmp(data[child+1], data[child])){
            child = child + 1;
        }
        // 比较父节点
        if(cmp(data[child], data[parent])){
            Swap(&data[child], &data[parent]);
        }else{
            break;
        }
        parent = child;
        child = parent * 2 + 1;
    }
}

void HeapInsert(Heap* heap, HeapType value){
    if(heap->size >= HeapMaxSize) return;
    heap->data[heap->size++] = value;
    AdjustUp(heap->data, heap->size, heap->cmp, heap->size-1);
}

void HeapSort2(HeapType array[], int size, Compare cmp){
    if(size<=1) return;

    // Create Heap
    int i=0;
    for(;i<size;i++) AdjustUp(array, i, cmp, i);

    // 2. 依次取出堆顶元素
    while(i>0){
        Swap(&array[0], &array[i-1]);
        i--;
        AdjustDown(array, i, cmp, 0);
    }

}